#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/10/07
# @Author   :Changshu
# @File     :practice_226.py

# 226. 翻转二叉树,翻转一棵二叉树

class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None


def preOrder(root: TreeNode):
	if root:
		print(root.val, end=' ')
		preOrder(root.left)
		preOrder(root.right)


def invertTree(root: TreeNode) -> TreeNode:
	if root is None:
		return None
	left = invertTree(root.left)
	right = invertTree(root.right)
	root.left = right
	root.right = left
	return root


if __name__ == '__main__':
	node1 = TreeNode(4)
	node2_1 = TreeNode(2)
	node2_2 = TreeNode(7)
	node3_1 = TreeNode(1)
	node3_2 = TreeNode(3)
	node3_3 = TreeNode(6)
	node3_4 = TreeNode(9)

	node1.left = node2_1
	node1.right = node2_2
	node2_1.left = node3_1
	node2_1.right = node3_2
	node2_2.left = node3_3
	node2_2.right = node3_4

	preOrder(node1)
	root = invertTree(node1)
	print()
	preOrder(root)
